package com.leetcode.ask;

import java.util.ArrayList;
import java.util.List;

/**
 * @ProjectName: leetcode
 * @Package: com.leetcode.ask
 * @description: 912. 排序数组
 * 给定一个整数数组 nums，将该数组升序排列。
 * 示例 1：
 * <p>
 * 输入：[5,2,3,1]
 * 输出：[1,2,3,5]
 * 示例 2：
 * <p>
 * 输入：[5,1,1,2,0,0]
 * 输出：[0,0,1,1,2,5]
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= A.length <= 10000
 * -50000 <= A[i] <= 50000
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sort-an-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: liyc
 * @CreateDate: 2020/1/31 6:23 PM
 * @Version: 1.0
 * <p>Copyright: Copyright (c) 2020</p>
 */
public class SortArray {
    /**
     * @param
     * @return
     * @description 冒泡排序：重复从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字位置的算法
     * 重点：从最右侧取出值，依次和左侧的比较，顺序交换
     * 快速排序 复杂度O(n^2) n^2/2
     * 结果：超出时间限制
     * @author liyc
     * @date 2020/1/31
     */
    public List<Integer> maoPao(int[] nums) {
        //冒泡排序
        for (int i = 0; i < nums.length; i++) {
            for (int j = nums.length - 1; j > 0; j--) {
                int t = nums[j];
                if (nums[j - 1] > t) {
                    nums[j] = nums[j - 1];
                    nums[j - 1] = t;
                }
            }
        }
        List<Integer> list = new ArrayList();
        for (int n : nums) {
            list.add(n);
        }
        return list;

    }

    /**
     * @param
     * @return
     * @description 选择排序：从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换
     * 重点：先选出最小值，然后和最左边的交换
     * 选择排序 复杂度O(n^2) n^2/2
     * 结果：超出时间限制
     * @author liyc
     * @date 2020/1/31
     */
    public static List<Integer> xuanZe(int[] nums) {
        //选择排序
        for (int j = 0; j < nums.length; j++) {
            int index = j;
            for (int i = j + 1; i < nums.length; i++) {
                if (nums[i] < nums[index]) {
                    index = i;
                }
            }
            int t = nums[j];
            nums[j] = nums[index];
            nums[index] = t;
            System.out.println("j:" + j + "t:" + t);
        }


        List<Integer> list = new ArrayList();
        for (int n : nums) {
            list.add(n);
            System.out.println(n);
        }
        return list;

    }

    /**
     * @param
     * @return
     * @description 插入排序：插入排序是一种从序列左端开始依次对数据进行排序的算法。
     * 重点：将数组划分为两个区域，左侧为插入区，右侧为待排区，依次从右侧取出数据，依次与插入区比较，大于则放右边，小于则放左边
     * 结果：通过，因为else有break，复杂度比冒泡和选择排序低
     * @author liyc
     * @date 2020/2/9
     */
    public static List<Integer> chaRu(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i; j >= 0; j--) {
                if (nums[j + 1] < nums[j]) {
                    int t = nums[j + 1];
                    nums[j + 1] = nums[j];
                    nums[j] = t;
                } else {
                    break;
                }
            }
        }
        List<Integer> list = new ArrayList();
        for (int n : nums) {
            list.add(n);
            System.out.println(n);
        }
        return list;
    }


   


    public static void main(String[] args) {
        int[] nums = new int[]{5, 2, 7, 3, 6, 1, 4};
        chaRu(nums);
    }


}
